package tiruvury.InterviewPrep.DataStructures;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
import java.util.ListIterator;

import tiruvury.InterviewPrep.HelperClasses.AnagramComparator;

public class MyStrings
{
	public static void PrintLeftJustifiedText(String str, int maxLen)
	{
		int countSoFar = 0;
		int wordStart = 0;
		int nextWordStart = 0;
		String nextWord = null;
		StringBuffer sb = new StringBuffer();

		while (nextWordStart < str.length())
		{
			nextWordStart = getNextWordStart(str, wordStart);
			/*
			 * SYNTAX ERROR: SUBSTRING WITH START AND END INDICES IS LIKE THIS:
			 * [StartIdx, EndIdx)
			 */
			nextWord = str.substring(wordStart, nextWordStart).trim();

			if (countSoFar + nextWord.length() + 1 <= maxLen)
			{
				if (sb == null)
				{
					sb = new StringBuffer();
				}
				sb.append(nextWord);
				sb.append(' ');
				countSoFar = countSoFar + nextWord.length() + 1;
				nextWord = null;
				wordStart = nextWordStart;
			}
			else
			{
				// Can't Process word. Print whatever you have and reset
				// countSoFar.
				System.out.println(sb.toString());
				sb = null;
				countSoFar = 0;
			}
		}

		if (sb != null && nextWord != null)
		{
			sb.append(nextWord);
			sb.append(' ');
			System.out.println(sb.toString());
		}
		else if (sb != null)
		{
			System.out.println(sb.toString());
		}
		else if (nextWord != null)
		{
			sb = new StringBuffer();
			sb.append(nextWord);
			sb.append(' ');
			System.out.println(sb.toString());
		}
	}

	private static int getNextWordStart(String str, int idx)
	{
		while (str.charAt(idx) == ' ')
		{
			idx++;
		}

		int nextSpace = str.indexOf(' ', idx);

		/*
		 * CODINGERROR: You forgot about the fact that the last word does not
		 * have a space after it. That needs to be handled separately.
		 */
		if (nextSpace == -1)
		{
			// End of string scenario.
			return str.length();
		}

		return nextSpace + 1;
	}

	public static boolean CanMakeRansomNote(String magazine, String note)
	{
		if (magazine != null && note != null)
		{
			magazine = magazine.trim();
			note = note.trim();

			int[] counts = new int[256];
			int uniqueCharCount = 0;
			char[] magArr = magazine.toCharArray();
			char[] noteArr = note.toCharArray();

			for (int i = 0; i < noteArr.length; i++)
			{
				if (noteArr[i] == ' ')
				{
					continue;
				}

				if (counts[noteArr[i]] == 0)
				{
					uniqueCharCount++;
				}
				counts[noteArr[i]]++;
			}

			for (int i = 0; i < magArr.length; i++)
			{
				if (magArr[i] == ' ')
				{
					continue;
				}

				if (counts[magArr[i]] != 0)
				{
					counts[magArr[i]]--;
					if (counts[magArr[i]] == 0)
					{
						uniqueCharCount--;

						if (uniqueCharCount == 0)
						{
							break;
						}
					}
				}
			}

			return (uniqueCharCount == 0);
		}

		return false;
	}

	public static String getLongestWord(String[] arr)
	{
		if (arr == null)
		{
			return null;
		}

		HashSet<String> hs = new HashSet<String>();
		int maxLen = 0;
		for (String str : arr)
		{
			maxLen = Math.max(str.length(), maxLen);
			hs.add(str);
		}

		return computeLongestWord(arr, hs, new HashSet<String>(), null, maxLen);
	}

	public static String computeLongestWord(String[] arr, HashSet<String> words, HashSet<String> processedWords, String word, int maxLen)
	{
		String str = null;
		String longestWord = "";
		if (word != null)
		{
			if (word.length() > maxLen)
			{
				return "";
			}

			if (words.contains(word) && processedWords.size() > 1)
			{
				longestWord = word;
			}
		}

		StringBuffer sb = null;
		HashSet<String> newProcWords = null;
		for (int i = 0; i < arr.length; i++)
		{
			if (!processedWords.contains(arr[i]))
			{
				sb = new StringBuffer();
				/*
				 * SYNTAX: Here's how you clone a HashSet
				 */
				newProcWords = (HashSet<String>) processedWords.clone();

				if (word != null && word != "")
				{
					sb.append(word);
				}
				sb.append(arr[i]);
				newProcWords.add(arr[i]);

				/*
				 * CODINGERROR: You added to the original hashset and passed it
				 * into the recursive function
				 * Now that list would be messed up in this function
				 */
				str = computeLongestWord(arr, words, newProcWords, sb.toString(), maxLen);

				if (str != null && str != "" && str.length() > longestWord.length())
				{
					longestWord = str;
				}
			}

		}

		return longestWord;
	}

	public static String encodeSpaces(String str)
	{
		if (str == null || str.isEmpty())
			return str;

		int spaceCount = getSpaceCount(str);
		if (spaceCount == 0)
			return str;

		char[] arr = new char[str.length() + 2 * spaceCount];
		/*
		 * SYNTAX: DONT USE array.clone() here as it will clone the original
		 * string and the new array
		 * will just be same as the old array even though its initialized a
		 * larger size with extra spaces.
		 */
		for (int i = 0; i < str.length(); i++)
		{
			arr[i] = str.charAt(i);
		}

		int i = str.length() - 1;
		int j = arr.length - 1;

		while (i >= 0 && j >= 0)
		{
			if (arr[i] == ' ')
			{
				if (j >= 2)
				{
					arr[j] = '0';
					arr[j - 1] = '2';
					arr[j - 2] = '%';
					j = j - 3;
				}
			}
			else
			{
				arr[j] = arr[i];
				j--;
			}
			i--;
		}

		return new String(arr);
	}

	private static int getSpaceCount(String str)
	{
		int spaceCount = 0;

		if (str != null)
		{
			for (int i = 0; i < str.length(); i++)
			{
				if (str.charAt(i) == ' ')
				{
					spaceCount++;
				}
			}
		}

		return spaceCount;
	}

	public static String reverseWords(String str)
	{
		if (str == null || str.length() == 1)
		{
			return str;
		}

		int wordStart = -1;
		int wordEnd = -1;
		int ch;
		for (int i = 0; i < str.length(); i++)
		{
			ch = str.charAt(i);
			if (ch == ' ')
			{
				if (wordStart != -1 && wordEnd == -1)
				{
					wordEnd = i - 1;
				}
			}
			else
			{
				if (wordStart == -1)
				{
					wordStart = i;
				}

				/*
				 * CODINGERROR: You missed this boundary case where the last
				 * character is a letter and not a space.
				 */
				if (i == str.length() - 1)
				{
					wordEnd = i;
				}
			}

			if (wordStart != -1 && wordEnd != -1)
			{
				// Reverse the individual word in place
				str = reverseInPlace(str, wordStart, wordEnd);
				wordStart = -1;
				wordEnd = -1;
			}
		}

		str = reverseInPlace(str, 0, str.length() - 1);
		return str;
	}

	private static String reverseInPlace(String str, int startIdx, int endIdx)
	{
		if (str == null || startIdx > endIdx || endIdx >= str.length())
		{
			return null;
		}

		char[] arr = str.toCharArray();
		char ch;
		/*
		 * CODINGERROR: ALWAYS USE A WHILE LOOP FOR STRING SWAPPING. LESS
		 * COMPLICATED. YOU DONT HAVE TO USE
		 * YOU DONT HAVE TO WORRY ABOUT COMPLICATIONS INVOLVING HANDLING START
		 * AND END INDICES IN THE MIDDLE OF THE STRING.
		 * FOR INSTANCE, i should be less than or equal to startIndex +
		 * endIndex/2 etc.
		 */
		/*
		 * for(int i = startIndex; i<= endIndex/2; i++)
		 * {
		 * ch = arr[i];
		 * arr[i] = arr[endIndex - i + 1];
		 * arr[endIndex-i+1] = ch;
		 * }
		 */

		int i = startIdx;
		int j = endIdx;
		while (i < j)
		{
			ch = arr[i];
			arr[i] = arr[j];
			arr[j] = ch;

			i++;
			j--;
		}

		return new String(arr);
	}

	public static boolean isPermutation(String s1, String s2)
	{
		if (s1 == null || s2 == null || s1.length() != s2.length())
		{
			return false;
		}

		int uniqueCharCount = 0;
		int[] arr = new int[256];

		int i;
		char ch;
		for (i = 0; i < s1.length(); i++)
		{
			ch = s1.charAt(i);
			if (arr[ch] == 0)
			{
				uniqueCharCount++;
			}
			arr[ch]++;

		}

		for (i = 0; i < s2.length(); i++)
		{
			ch = s2.charAt(i);
			if (arr[ch] == 0 || uniqueCharCount == 0)
			{
				return false;
			}
			if (arr[ch] == 1)
			{
				uniqueCharCount--;
			}
			arr[ch]--;
		}

		if (uniqueCharCount > 0)
		{
			return false;
		}

		return true;
	}

	public static boolean HasUniqueChars(String str) throws IOException
	{
		if (str == null || str.length() == 0)
			return false;

		/*
		 * Bit Vector solution works only if the string has letters from the
		 * alphabet a-z
		 */
		/* this check is case-insensitive */
		str = str.toLowerCase();

		int bitVector = 0;
		boolean duplicateCharFound = false;
		int charPos;
		char ch;
		for (int i = 0; i < str.length(); i++)
		{
			ch = str.charAt(i);

			if (ch < 'a' || ch > 'z')
			{
				throw new IOException("Input string has non-alphabet characters");
			}

			charPos = ch - 'a';

			/*
			 * CODINGERROR: You cannot say if (bitVector & charValue). That
			 * doesn't by default resolve to a boolean.
			 * This is *not* JavaScript!!
			 */
			if ((bitVector & (1 << charPos)) == 1)
			{
				duplicateCharFound = true;
				break;
			}
			bitVector |= (1 << charPos);
		}

		return !duplicateCharFound;
	}

	public static boolean HasUniqueChars2(String str) throws IOException
	{
		if (str == null || str.length() == 0)
			return false;

		/*
		 * Assuming input can be over ASCII charset
		 */

		/*
		 * CODING ERROR: BE VERY CAREFUL with what ur initializing. You first
		 * initialized to an 8 byte array - which means only 8*8 = 64 values.
		 * You need a 32 byte array so that u get 8 * 32 = 256 chars
		 */
		byte[] bitMaskArr = new byte[32];
		boolean duplicateCharFound = false;
		char ch;
		int maskArrIdx = -1;
		int bitPos = -1;
		for (int i = 0; i < str.length(); i++)
		{
			ch = str.charAt(i);

			if ((int) ch > 255)
			{
				throw new IOException("Input string has a non-ASCII character");
			}

			maskArrIdx = (int) ch / 8;
			bitPos = (int) ch % 8;

			/*
			 * CODINGERROR:
			 * 1) You cannot say if (bitVector & bitMaxk). That
			 * doesn't by default resolve to a boolean.
			 * 2) You ALSO cannot say (bitVector & bitMask) == 1, as it will not
			 * be 1.
			 * You should say (bitVector & bitMask) == bitMask
			 * This is *not* JavaScript!!
			 */
			if ((bitMaskArr[maskArrIdx] & (1 << bitPos)) == (1 << bitPos))
			{
				duplicateCharFound = true;
				break;
			}
			bitMaskArr[maskArrIdx] |= (1 << bitPos);
		}

		return !duplicateCharFound;
	}

	public static char[] reverse(char[] arr)
	{
		if (arr == null)
			return null;

		int len = arr.length;
		int i;
		char ch;
		for (i = 0; i < (len / 2); i++)
		{
			ch = arr[i];
			arr[i] = arr[len - 1 - i];
			arr[len - 1 - i] = ch;
		}

		return arr;
	}

	public static int FindWordFrequency(String book, String word)
	{
		if (book == null || word == null)
			return -1;

		book = book.toLowerCase();
		word = word.toLowerCase();

		/*
		 * SYNTAX: Splitting a string (split s is small)
		 * str.split()
		 */
		String[] bookArr = book.split(" ");
		String[] wordArr = word.split(" ");

		if (wordArr.length > 1)
		{
			return -1;
		}

		Hashtable<String, Integer> ht = new Hashtable<String, Integer>(bookArr.length);
		for (String bookStr : bookArr)
		{
			/*
			 * CODINGERROR: Trim any leading/trailing spaces
			 */
			bookStr = bookStr.trim();

			/*
			 * CODINGERROR: Always use containsKey() and not contains()
			 */
			if (ht.containsKey(bookStr))
			{
				ht.put(bookStr, ht.get(bookStr) + 1);
			}
			else
			{
				ht.put(bookStr, 1);
			}
		}

		word = word.trim();
		if (ht.containsKey(word))
		{
			return ht.get(word);
		}

		return -1;
	}

	// Find needle in Haystack
	public static char[] StrStr(char[] haystack, char[] needle)
	{
		/*
		 * CODINGERROR: Always initialize the character array with some size. Or
		 * else it will be a 0-sized array
		 * and will throw indexoutofbounds exceptions when being assigned values
		 * in indices.
		 */
		char[] result = new char[haystack.length];
		int idx = -1;

		if (haystack.length != 0 && needle.length != 0)
		{
			int j = 0;
			for (int i = 0; i < haystack.length; i++)
			{
				if (j == needle.length)
				{
					break;
				}

				/*
				 * CODINGERROR: This is how you convert a character to lowercase
				 * Character.toLowerCase
				 */
				if (Character.toLowerCase(needle[j]) == Character.toLowerCase(haystack[i]))
				{
					if (idx == -1)
					{
						idx = i;
					}
					j++;
				}
				else
				{
					if (idx != -1)
					{
						/*
						 * CODINGERROR: if the current character doesn't match
						 * the needle, we must reconsider
						 * every letter right after idx for comparison.
						 * 
						 * AND DONT, LIKE AN IDIOT DO IDX+1 as the for loop will
						 * also increment it.
						 */
						i = idx;
						idx = -1;

					}

					j = 0;
				}

				/*
				 * CODINGERROR
				 * WHY THE FUCK DID YOU ADD AN I++ HERE WHEN YOU ARE ALREADY
				 * HAVE ONE ON THE TOP IN THE FORLOOP?
				 * REMOVING IT NOW.
				 */
			}
		}

		if (idx != -1)
		{
			int k = idx;
			for (; k < haystack.length; k++)
			{
				result[k - idx] = haystack[k];
			}
			/*
			 * CODINGERROR! BIG ONE! You must end the string with \0
			 * NOTE the SLASH: its \0
			 */
			result[k - idx] = '\0';
		}

		return result;
	}

	public static String[] SortByAnagrams(String[] strings)
	{
		Arrays.sort(strings, new AnagramComparator());
		return strings;
	}

	public static String[] SortByAnagrams1(String[] strings)
	{
		/*
		 * SYNTAX: See how you declared a Hashtable with String -> List, wherein
		 * the List itself is a list of strings.
		 */
		Hashtable<String, List<String>> ht = new Hashtable<String, List<String>>();
		for (String str : strings)
		{
			char[] ch = str.toCharArray();
			Arrays.sort(ch);
			String newStr = new String(ch).toLowerCase();
			if (ht.containsKey(newStr))
			{
				ht.get(newStr).add(str);
			}
			else
			{
				/*
				 * SYNTAX: How to initialize and ArrayList
				 */
				List<String> list = new ArrayList<String>();
				list.add(str);
				ht.put(newStr, list);
			}

			/*
			 * SYNTAX: How to get all keys in a hashtable? .keySet()
			 * How to get all values in a hashtable? .values()
			 */
			int idx = 0;
			for (List<String> list : ht.values())
			{
				/*
				 * SYNTAX: ListIterator usage Check.
				 */
				ListIterator<String> iter = list.listIterator(0);
				while (iter.hasNext())
				{
					strings[idx++] = iter.next();
				}
			}
		}
		return strings;
	}

	public static String compressString(String str)
	{
		/*
		 * SYNTAX: length is for arrays and length() is for Strings.
		 */
		if (str == null || str.length() == 0)
		{
			return null;
		}

		str = str.toLowerCase();
		char[] arr = str.toCharArray();
		char[] newArr = new char[2 * arr.length + 1];

		int count = 0;
		int newIdx = 0;
		char ch = arr[0];
		for (int idx = 0; idx < arr.length; idx++)
		{
			if (arr[idx] == ch)
			{
				count++;
			}

			if (arr[idx] != ch || idx == arr.length - 1)
			{
				newArr[newIdx++] = ch;
				/*
				 * CODINGERROR: When doing an itoa on an integer, you cannot do
				 * this:
				 * char[] arr = (char)('0' + intValue);
				 * Reason is: intValue can be more than 9, and this will break.
				 * You will have to convert the int to a string, then to a char
				 * array.
				 */
				char[] cntArr = Integer.toString(count).toCharArray();
				for (char intCh : cntArr)
				{
					newArr[newIdx++] = intCh;
				}

				ch = arr[idx];
				count = 1;
			}
		}
		newArr[newIdx] = '\0';

		String newStr = new String(newArr);
		return (str.length() <= newStr.length()) ? str : newStr;
	}

	public static String compressString2(String str)
	{
		/*
		 * SYNTAX: length is for arrays and length() is for Strings.
		 */
		if (str == null || str.length() == 0)
		{
			return null;
		}

		str = str.toLowerCase();
		StringBuffer sb = new StringBuffer();
		boolean returnOriginalString = false;

		int count = 0;
		char prevCh = str.charAt(0);
		char currCh = str.charAt(0);
		for (int idx = 0; idx < str.length(); idx++)
		{
			currCh = str.charAt(idx);

			if (currCh == prevCh)
			{
				count++;
			}
			else
			{
				sb.append(prevCh);
				sb.append(count);
				prevCh = currCh;
				count = 1;
			}

			if (sb.length() >= str.length())
			{
				returnOriginalString = true;
				break;
			}
		}
		sb.append(currCh);
		sb.append(count);

		return (returnOriginalString) ? str : ((sb.length() >= str.length()) ? str : sb.toString());
	}

	public static void PrintPermutations(String chars)
	{
		String seenSoFar = "";
		DoPermute(chars, seenSoFar);
	}

	public static boolean CheckDuplicateCharsBruteForce(String str)
	{
		str = str.toLowerCase();
		char[] arr = str.toCharArray();
		boolean duplicateCharFound = false;

		for (int i = 0; i < arr.length; i++)
		{
			/*
			 * CODINGERROR
			 * Not an error, but instead of i != j inside, you can even
			 * initialize j to i + 1.
			 * It wont cause an outofbounds, as the condition check takes care
			 * of it.
			 */
			for (int j = i; j < arr.length; j++)
			{
				if (i != j)
				{
					if (arr[i] == arr[j])
					{
						duplicateCharFound = true;
						break;
					}
				}
			}

			if (duplicateCharFound)
			{
				break;
			}
		}

		return duplicateCharFound;
	}

	public static boolean CheckDuplicateCharsOptimal(String str)
	{
		str = str.toLowerCase();
		boolean duplicateCharFound = false;
		Hashtable<Character, Integer> charCount = new Hashtable<Character, Integer>();

		for (int i = 0; i < str.length(); i++)
		{
			Character ch = new Character(str.charAt(i));
			if (charCount.containsKey(ch))
			{
				duplicateCharFound = true;
				break;
			}
			else
			{
				charCount.put(ch, new Integer(1));
			}
		}

		return duplicateCharFound;
	}

	private static void DoPermute(String chars, String seenSoFar)
	{
		for (int i = 0; i < chars.length(); i++)
		{
			char ch = chars.charAt(i);
			/*
			 * CODINGERROR:
			 * REPETITION!!!!
			 * When using recursion, DO NOT, I REPEAT, DO NOT change the value
			 * of the parameter passed in. In this case, seenSoFar needs to be
			 * updated in each iteration. So if you change it in the first
			 * iteration it affects the remaining iterations. You have to CACHE
			 * IT first!
			 */
			String permutation = seenSoFar;
			/*
			 * CODINGERROR:
			 * How to check if a string contains a character or not?
			 * Answer: indexOf()
			 */
			if (seenSoFar.indexOf(ch) == -1)
			{
				permutation = permutation + ch;
				System.out.println(permutation);
				DoPermute(chars, permutation);
			}
		}
	}

}
